The development and application of rule engines is one branch of Artificial Intelligence (A.I.), which is a very broad research area that focuses on “making computers think like people.” Broadly speaking, a rule engine processes information by applying rules to data objects (also known as facts; or simply referred to as data). A rule is a logical construct for describing the operations, definitions, conditions, and/or constraints that apply to some predetermined data to achieve a goal. Various types of rule engines have been developed to evaluate and process rules. Conventionally, a rule engine implements a network to process rules and data objects, which can also be referred to as facts. A network may include many different types of nodes, including, for example, object-type nodes, alpha nodes, left-input-adapter nodes, eval nodes, join nodes, not nodes, accumulate nodes, and terminal nodes, etc. Some conventional rule engines build Rete networks, and hence, are referred to as Rete rule engines.
Typically, data objects enter a network at the root node, from which they are propagated to any matching object-type nodes. From an object-type node, a data object is propagated to either an alpha node (if there is a literal constraint), a left-input-adapter node (if the data object is the left most object type for the rule), or a beta node (such as a join node).
A beta node has two inputs, unlike one-input nodes, such as object-type nodes and alpha nodes. A beta node can receive tuples in its left-input and data objects, or simply referred to as objects, in its right-input. A tuple is a single-dimensional data structure containing a set of facts that have matched a rule. Join nodes, not nodes, and exist nodes are some examples of beta nodes. All nodes may have one or more memories to store a reference to the data objects and tuples propagated to them, if any. For example, a beta node can have a left memory and a right memory associated with its left input and right input, respectively. The left-input-adapter node creates a tuple with a single data object and propagates the tuple created to the left input of the first beta node connected to the left-input-adapter node, where the tuple is placed in the left memory of the beta node and then join attempts are made with all the objects in the right memory of the beta node.
When another data object enters the right input of the join node, the data object is placed in the right memory of the join node and join attempts are made with all the tuples in the left memory of the join node. The tuples placed in the left memory of the join node are partially matched. If a join attempt is successful, the data object is added to the tuple, which is then propagated to the left input of the next node in the network. Such evaluation and propagation continue through other nodes down the network, if any, until the tuple reaches the terminal node. When the tuple reaches the terminal node, the tuple is fully matched. At the terminal node, an activation is created from the fully matched tuple and the corresponding rule. The activation is placed onto an agenda of the rule engine for potential firing or potential execution.
As mentioned above, a tuple contains a set of facts that match a rule. So, for example, consider the following pseudo code of a rule:
RuleXWhenCustomer ( ) andOrder ( ) andShippingAddress ( )Then// perform some operationsEndThe above rule can match each combination of Customer, Order, and ShippingAddress facts in the working memory. These combinations are called tuples and can be represented in the following way:    Tuple1=[customer1, order1, shippingaddress1],where Tuple1 is an arbitrary name given to the tuple, customer1 is an instance of Customer, order1 is an instance of Order, and ShippingAddress is an instance of ShippingAddress.
All tuples matching the above rule always have its component facts in the exact order in which they match the patterns in the rule. Thus, a numeric index can be defined for each element in the tuple. The numeric index is also referred to as an “offset.” So, the first fact in a tuple has offset 0, the second fact has offset 1, and so on. Referring back to the above example, individual elements of Tuple1 can thus be referenced by:    Tuple1[0]=customer1;    Tuple1[1]=order1;    Tuple1[2]=shippingaddress1
Although the above conventional tuple can be used for a wide range of applications, there are situations in which it is not powerful or flexible enough. For instance, when support to repetitions are necessary, such as:    A( ) and [1-10]B( ) and C( ),where A( ), B( ), and C( ) are patterns of the rule in the current example, which intends to match one A, between 1 and 10 B's and one C. Suppose in one working memory, there are two (2) B's matching the above rule, and thus, the following tuple may be resulted:    T2=[a1, b1, b2, c1]For another working memory, there are three B's matching the above rule, and thus, the following tuple may be resulted:    T3=[a1, b1, b2, b3, c1]
As shown in the above example, the tuples T2 and T3 have different lengths and offsets between different instantiations of the working memory. For instance, c1 would have offset 3 in T2, and 4 in T3. This would also cause problems for rule authors because it would be difficult, if not impossible, for them to unambiguously address elements in such tuples.